优化模型

2020 B题“保护生物多样性”(Funding Biodiversity Conservation)总体而言是一个优化问题,即在给定约束条件下寻找到可以使目标函数取得最大值或最小值的变量取值。
基于目标函数和约束条件,可以将优化问题分为:

基于目标函数个数,可以分为:

基于约束条件的有无,可以分为:

针对2020年B题而言,其目标简单梳理可以包括:花费最少、效率最高、收益最大等,是一个多目标规划问题,不过经过精心整合可以将上述目标整合为单一目标,这样也易于求解。一般来看,同学们所建立的模型都是非线性的且有约束的模型。优化问题一般不好解,编程量也比较大,往往需要使用合适的优化算法进行求解(如蒙特卡洛模型算法、基因算法等)。

不过除了总体上的优化模型以外,该问题的部分环节或子问题也可以利用到其他模型,比如确定目标函数时可以使用评价模型的思路,对未来资金的预期可以使用预测模型。

优化模型的要素

优化模型的基本要素包括:

决策变量

我们首先来看B题的决策变量。本题我们核心的目标是“Develop a model or algorithm (or set of models or algorithms) for the FRPCE Board to use to determine a fundraising schedule that will minimize the funds required to be raised”,"schedule"是要做出的决策。"schedule"就是时间表,表示什么时间做什么事情,具体到这个问题,那就是“每一年要资助哪些物种的保护计划”或者说“每个物种的保护计划从哪年开始到哪年结束”,进一步提炼,决策变量实际就是“不同物种保护计划开始的时间”(根据问题,一般会假定计划若开始,就会一直实施到给定期限以后)。现在我们考虑48个物种在30年间的保护计划,那就可以设48个变量表示48个物种保护计划开启时间,每个变量可选的值的范围为1,2,3,....,30.若有m个物种n年计划,那就是m个变量,变量取值范围为1至n的整数。

目标函数

前面谈到本题应该算是多目标规划问题,因为决策者既希望筹集资金越少越好,又希望保护的物种越多越好,再分析下去还可能有每年的资金投入越稳定越好以及完成所有物种保护的总年数越短越好。这些目标之间很可能还有“冲突”,比如资金越少,那么保护的物种也很有可能是越少的,再如总年数越短,那极有可能每年的投入就越大。平衡这些目标很棘手,但往往现实问题就是这样,我们必须要找到“平衡”这些目标的方法。对于多目标问题,一种常用的处理策略是让某些目标变成约束条件,将多目标问题转化为单目标问题,具体策略如下:

  1. 以效益最大为目标,将成本控制在给定值以下。在本题中可以是在给定资助总额或年资助额(比如100万)以下,以救的物种最多或获得的救助效益最大为目标;
  2. 以成本最低为目标,将效益控制在给定值以上。本题中可以是要求至少拯救物种数量(比如40个)或给定效益值(视具体情境而定),使得总资助额或年资助额最小为目标;
  3. 对收益和成本因素进行综合,将冲突目标转化为一个整合目标。比如给定收益一个权重,成本一个权重,将加权后的收益减去加权后的成本作为目标,或者使用收益/成本,计算投入产出比性价比作为目标,使其越大越好。

约束条件

谈到约束条件,我们不得不先谈一下这个问题的求解假设,同学们也可以借这个案例假设的分析,深入理解“模型假设”的功能与含义。现实世界的问题总是复杂的,需要我们去分析理清,在理清的过程中我们会发现很多信息我们是不知道的或者不确定的,这些信息也无法通过我们的模型求解得到,反而模型的建立却要依赖这些信息,此时我们就可以“假设”这些信息是怎样的,然后接下来推进建模过程。

2020年B题就有如下假设:

上述这个假设有没有问题?有问题,生活经验告诉我们,“计划赶不上变化”,说好的要连续资助三年,但可能第二年发生战争了、政府换届了政策改变了或者其他意外的情况,那中断资助是很有可能的。 但上述假设合不合理?也合理,毕竟我们没有办法把所有意外情况都考虑到,或者我们都考虑到那方案和建模可以设想会很复杂,超出了建模者的能力范畴,这样的假设可以视为对现实的一个“近似”,也可以理解。总体来看,这个假设还是比较合理的,如果你偏要说我“考虑不周”,我也认了,而且把这个“不周”就放在“模型假设”这个环节等待大家的批判或理解。

另一个重要的假设是:

一个物种的救助成功率“Feasibility of Success”会不会随时间改变?可能会,也可能不会,但我倾向认为它会,从常识可以知道既然是濒危物种了,你不去拯救它就相当于它自生自灭,情况大概率会越来越糟。救得早,那挽救它的几率就大,救得晚可能就救不回来了。当然有人会说“无心插柳柳成荫”,说不定你不管它,它活得还越好呢!也不是没可能,但也不和你在这里“杠”,我把这条放在这里做“假设”,让大家知道我模型的基础是什么,“欢迎批评指正”。

“模型假设”给问题做了简化和清晰化,优化问题的约束条件也要考虑到“假设”提供的便利与约束。当然,也还有上述为了将多目标转换为单目标过程中产生的一些约束。

具体而言,对于本题的约束可以包括:

等等。

优化模型

非线性规划模型的一般形式描述如下: $$ \begin{aligned} &\min f(x), \\ &\text { s.t. } \begin{cases}g_{i}(x) \leq 0, & i=1,2, \cdots, m, \\ h_{j}(x)=0, & j=1,2, \cdots, l,\end{cases} \end{aligned} $$ 其中 $x=\left[x_{1}, x_{2}, \cdots, x_{n}\right]^{T} \in R^{n}$, 而 $f, g_{i}, h_{j}$ 都是定义在 $R^{n}$ 上的实值函数。

以O奖论文中的模型为例,我们看一下解决本问题模型的形式:

10997

“投入产出比”式的目标函数 $$ E B=\sum_{i \in S} \frac{\left(w_{1}^{\prime} b_{i}+w_{2}^{\prime} u_{i}\right) f_{i}}{c_{i}} $$ 其中 $S$ 决定救助的物种集合, $w_{1}^{\prime}=\frac{w_{1}}{w_{1}+w_{2}}$ , $w_{2}^{\prime}=\frac{w_{2}}{w_{1}+w_{2}}$其中 $w_{1}$ 和 $w_{2}$ 分别是“Benefit” $b_{i}$的权重以及“Taxonomic uniqueness” $u_{i}$ 的权重. $f_{i}$ 是第 $i$个项目开始救助的时间, $c_{i}$ 是第 $i$ 个项目的花费. $E B$考虑了除项目总年数以外的所有因素。

10876

优化模型的优化目标 $$ \max \sum_{i=1}^{N} \frac{B_{i} \cdot S_{i}\left(k_{i}\right)}{P_{i}} $$ 用$R_{i}$ 表示第 $i$ 从第$k_{i}$ 年开始实施项目的成本效用.$R_{i}$又可以写成 $$ R_{i}\left(k_{i}\right)=\frac{B_{i} \cdot S_{i}\left(k_{i}\right)}{P_{i}} $$ 其中$B_{i}$是第$i$个项目的”Benefit“,$S_{i}\left(k_{i}\right)$是第 $i$ 从第$k_{i}$ 年开始实施项目的成功率,${P_{i}$是第$i$个项目的花费。

10839

目标函数为 $$ \max b t=\sum_{i=1}^{48} b t_{i},i \in[1,48] $$ 其中 $$ b t_{i}=x_{i, 0} \cdot f_{i} \cdot\left(1-r_{b} u_{i}\right)^{s_{i}-1} $$ $x_{i, 0}$是第$i$个项目初始的“Benefit”, $f_{i}$ 是第$i$个项目的成功率, $u_{i}$ 是第$i$个项目的独特性.$\left(1-r_{b} u_{i}\right)^{s_{i}-1}$ 表示“折旧系数”即随着起始救助时间的推迟,项目的收益呈指数递减. $r_{b}$,$s_{i}$是设定的参数。